
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1681. -- [Usaco2005 Mar]Checking an Alibi -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1681: [Usaco2005 Mar]Checking an Alibi</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>29&nbsp;&nbsp;<span class=green>Solved: </span>24<br>[<a href='submitpage.php?id=1681'>Submit</a>][<a href='problemstatus.php?id=1681'>Status</a>][<a href='bbs.php?id=1681'>Discuss</a>]</center><h2>Description</h2><div class=content>
A crime has been comitted: a load of grain has been taken from the barn by
one of FJ's cows.  FJ is trying to determine which of his C (1 <= C <=
100) cows is the culprit.  Fortunately, a passing satellite took an image
of his farm M (1 <= M <= 70000) seconds before the crime took place, giving
the location of all of the cows.  He wants to know which cows had time to
get to the barn to steal the grain.

Farmer John's farm comprises F (1 <= F <= 500) fields numbered 1..F
and connected by P (1 <= P <= 1,000) bidirectional paths whose
traversal time is in the range 1..70000 seconds (cows walk very
slowly).  Field 1 contains
the barn.  It takes no time to travel within a field (switch paths).

Given the layout of Farmer John's farm and the location of each cow
when the satellite flew over, determine set of cows who could be
guilty.

NOTE: Do not declare a variable named exactly 'time'. This will reference
the system call and never give you the results you really want.

</div><h2>Input</h2><div class=content>
* Line 1: Four space-separated integers: F, P, C, and M

* Lines 2..P+1: Three space-separated integers describing a path: F1,
        F2, and T. The path connects F1 and F2 and requires T seconds
        to traverse.

* Lines P+2..P+C+1: One integer per line, the location of a cow.  The
        first line gives the field number of cow 1, the second of cow
        2, etc.

</div><h2>Output</h2><div class=content>
* Line 1: A single integer N, the number of cows that could be guilty
        of the crime.

* Lines 2..N+1: A single cow number on each line that is one of the
        cows that could be guilty of the crime. The list must be in
        ascending order.

</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata><br />
7 6 5 8<br />
1 4 2<br />
1 2 1<br />
2 3 6<br />
3 5 5<br />
5 4 6<br />
1 7 9<br />
1<br />
4<br />
5<br />
3<br />
7<br />
<br />
INPUT DETAILS:<br />
<br />
Fields/distances like this:<br />
          6<br />
      4------5<br />
      |      |<br />
     2|      |<br />
      |      |<br />
7-----1      |5<br />
   9  |      |<br />
     1|      |<br />
      |      |<br />
      2------3<br />
          6<br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata><br />
4<br />
1<br />
2<br />
3<br />
4<br />
<br />
OUTPUT DETAILS:<br />
<br />
Any cow except cow 5 could have done it.  Cow 5 would take 9 seconds to get<br />
to the barn.</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Silver'>Silver</a></p></div><center>[<a href='submitpage.php?id=1681'>Submit</a>][<a href='problemstatus.php?id=1681'>Status</a>][<a href='bbs.php?id=1681'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
